/**
 * @author LKQ
 * @date 2022/1/2 9:27
 * @description 超出时间限制
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.lastRemaining(10));
    }

    public int lastRemaining(int n) {
        int[] arr = new int[n];
        for (int i = 1; i <= n; i++) {
            arr[i-1] = i;
        }
        return help(arr, true);
    }

    public int help(int[] arr, boolean left) {
        int n = arr.length;
        if (n == 1) {
            return arr[0];
        }
        int[] newArr = new int[n / 2];
        if (left) {
            // 从左到右
            for (int i = 0; i < n / 2; i++) {
                newArr[i] = arr[2 * i + 1];
            }
            left = false;
        }else {
            // 从右到左
            for (int i = 0; i < n / 2; i++) {
                if (arr.length  % 2 == 1) {
                    newArr[i] = arr[2*i + 1];
                }else {
                    newArr[i] = arr[2*i];
                }
            }
            left = true;
        }
        return help(newArr, left);
    }
}
